package zuoshen_video;
import org.junit.Test;

import tree.TreeNode;
import tree.TreeUtils;
public class MirrorsTraverse {
    /* 
        Mirros遍历，即线索二叉树遍历
        通过在空指针节点添加上层指针可以做到：
        1. 再次访问上层节点
        2. 判断第几次访问上层节点
        3. 不依赖栈遍历所有树节点
     */
    public void preOrder (TreeNode root) {
        if (root == null) return;
        TreeNode cur = root, rightest = null;
        while (cur != null) {
            if (cur.left != null) {
                rightest = findRightestInLeftTree(cur);
                if (rightest.right == null) {
                    
                    //在遍历左子树之前遍历根节点，就是前序遍历
                    System.out.println(cur.val);

                    //表名这个子树还没有访问，将其右子树设为自己
                    rightest.right = cur;
                    //访问左子树
                    cur = cur.left;
                } else {
                    //rightest.right == cur,说明该子树已经访问过，修复原指针，并访问右子树
                    rightest.right = null;
                    cur = cur.right;
                }
            } else {
                System.out.println(cur.val);
                cur = cur.right;
            }
        }
    }

    //换一种更优秀的写法

    /* 
        好像无论怎么写，要想打印完所有的节点，都必须要在两个地方打印：
        1. 有左子树，且左子树未被遍历过；
        2. 没有左子树；
        也都是二者的第一次。
    */
    public void preOrder2 (TreeNode root) {
        if (root == null) return;
        TreeNode cur = root, lastRight = null;
        while (cur != null) {
            lastRight = cur.left;
            if (lastRight != null) {
                //得到左子树最右子节点
                while (lastRight.right != null && lastRight.right != cur) lastRight = lastRight.right;
                if (lastRight.right == null) {
                    //左子树没有访问过
    
                    //前序遍历，先打印根节点
                    System.out.println(cur.val);
                    lastRight.right = cur;
                    cur = cur.left;
                    continue;//继续遍历左子树
                } else {
                    //左子树已经被访问过
                    lastRight.right = null;
                }
            } else System.out.println(cur.val);
            //左子树为空、左子树遍历完毕都会来到这里
            cur = cur.right;
        }
    }

    //寻找左子树的最右节点，是mirrors实现逻辑的关键
    public TreeNode findRightestInLeftTree(TreeNode cur) {
        if (cur.left == null) return null;
        TreeNode temp = cur;
        cur = cur.left;
        //cur不能回到
        while (cur.right != null && cur.right != temp) cur = cur.right;
        return cur;
    }

    //第二次访问cur，或者没有左子树时打印cur
    //由于这部分最终都会达到循环外面那个"大一统"位置，因此可以放在一起处理
    public void inOrder (TreeNode root) {
        if (root == null) return;
        TreeNode cur = root, lastRight = null;
        while (cur != null) {
            lastRight = cur.left;
            if (lastRight != null) {
                //得到左子树最右子节点
                while (lastRight.right != null && lastRight.right != cur) lastRight = lastRight.right;
                if (lastRight.right == null) {

                    lastRight.right = cur;
                    cur = cur.left;
                    continue;//继续遍历左子树
                } else {
                    //左子树已经被访问过
                    lastRight.right = null;
                }
            }
            //左子树为空、左子树遍历完毕都会来到这里
            System.out.println(cur.val);
            cur = cur.right;
        }
    }

    //第二次访问时，打印左子树右边界逆序；
    //最后额外打印根节点的右边界逆序
    class PostOrder {
        public void postOrder(TreeNode root) {
            if (root == null) return;
            TreeNode cur = root, lastRight = null;
            while (cur != null) {
                lastRight = cur.left;
                if (lastRight != null) {
                    while (lastRight.right != null && lastRight.right != cur) lastRight = lastRight.right;
                    if (lastRight.right != cur) {
                        lastRight.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                        lastRight.right = null;
                        printRightBoundary(cur.left);
                    }
                }
                cur = cur.right;
            }
            printRightBoundary(root);
        }

        public void printRightBoundary (TreeNode root) {
            root = reverseRightBoundary(root);
            TreeNode cur = root;
            while (cur != null) {
                System.out.println(cur.val);
                cur = cur.right;
            }
            root = reverseRightBoundary(root);
        }

        //通过迭代方法逆序一棵树的右边界
        public TreeNode reverseRightBoundary(TreeNode root) {
            TreeNode pre = root, post = root.right, temp;
            while (post != null) {
                temp = post.right;
                post.right = root;
                root = post;
                // pre.right = temp;
                post = temp;
            }
            pre.right = null;
            return root;
        }
    }


    @Test
    public void test() {
        TreeNode root = TreeUtils.createTree(new Integer[]{5, 4, 8, 11, null, 13, 4, 7, null, null, null, null, 1});
        TreeUtils.printBinaryTreeVisualization(root);
        // preOrder(root);
        // preOrder2(root);
        // inOrder(root);
        // System.out.println("=================================");
        new PostOrder().postOrder(root);
        // TreeUtils.printBinaryTreeVisualization(root);
    }
}
